package com.cat.dataStructure03;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/gcd-sort-of-an-array/
 * @create 2025/11/18 16:07
 * @since JDK17
 */

public class Solution85 {
    static int N = ((int) 1e5);
    static int[]lpf = new int[N + 1], f;
    Map<Integer, int[]> map = new HashMap<>();
    int[][] record;
    int cnt = 0;
    static {
        for (int i = 2; i <= N; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j <= N; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }
    }
    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }
    boolean isSame(int x, int y) {
        return find(x) == find(y);
    }
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        f[fx] = fy;
    }
    public boolean gcdSort(int[] nums) {
        int n = nums.length, max = Arrays.stream(nums).max().getAsInt();
        f = new int[n + max + 1];
        for (int i = 0; i < n + max + 1; i++) {
            f[i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int x = nums[i], p = lpf[x]; p > 1; x /= p, p = lpf[x]) {
                merge(i, n + p);
            }
        }
        Integer[] sorted = new Integer[n];
        Arrays.setAll(sorted, i -> i);
        Arrays.sort(sorted, Comparator.comparingInt(a -> nums[a]));
        for (int i = 0; i < n; i++) {
            if (!isSame(i, sorted[i])) {
                return false;
            }
        }

        return true;
    }
}
